/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MyCalendarIIIBST {
	class Node {
		int left, right;
		int count;
		Node leftChild, rightChild;

		public Node(int l, int r, int c) {
			left = l;
			right = r;
			count = c;
		}

		public void increaseCount() {
			this.count++;
			maxK = Math.max(maxK, count);
		}
	}

	int maxK = 1;
	Node root;

	public int book(int start, int end) {
		root = insert(root, start, end, 1);
		return maxK;
	}

	private Node insert(Node root2, int start, int end, int c) {
		if (start >= end) {// no need to take action
			return root2;
		}
		if (root2 == null) {
			root2 = new Node(start, end, c);
			return root2;
		}
		int l = root2.left;
		int r = root2.right;
		if (end <= l) {
			root2.leftChild = insert(root2.leftChild, start, end, c);
		} else if (start >= r) {
			root2.rightChild = insert(root2.rightChild, start, end, c);
		} else {
			int[] a = new int[4];
			if (start <= l) {
				a[0] = start;
				a[1] = l;
			} else {
				a[0] = l;
				a[1] = start;
			}
			if (end <= r) {
				a[2] = end;
				a[3] = r;
			} else {
				a[2] = r;
				a[3] = end;
			}
			root2.left = a[1];
			root2.right = a[2];

			root2.leftChild = insert(root2.leftChild, a[0], a[1], start <= l ? c : root2.count);
			root2.rightChild = insert(root2.rightChild, a[2], a[3], end >= r ? c : root2.count);
			root2.count += c;
			maxK = Math.max(maxK, root2.count);
		}
		return root2;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyCalendarIIIBST MyCalendarThree = new MyCalendarIIIBST();
		System.out.println(MyCalendarThree.book(10, 20)); // returns 1
		MyCalendarThree.book(50, 60); // returns 1
		System.out.println(MyCalendarThree.maxK);
		MyCalendarThree.book(10, 40); // returns 2
		System.out.println(MyCalendarThree.maxK);
		MyCalendarThree.book(5, 15); // returns 3
		System.out.println(MyCalendarThree.maxK);
		MyCalendarThree.book(5, 10); // returns 3
		System.out.println(MyCalendarThree.maxK);
		MyCalendarThree.book(25, 55); // returns 3
		System.out.println(MyCalendarThree.maxK);
	}

}
